public class Test3 {
    //leetcode 279 完全平方数
    public int numSquares(int n) {
        //题目可以理解为从i个平方数中选择，使得平方数的和恰好为n的完全平方数的最少数量
        //平方数的值为体积和价值，n为背包容量
        int aim = (int)Math.sqrt(n),INF = 0x3f3f3f3f;
        int[][] dp = new int[aim + 1][n + 1];
        for (int j = 1; j <= n; j++) dp[0][j] = INF;
        for (int i = 1; i <= aim; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][j - i * i] + 1);
                }
            }
        }
        return dp[aim][n];
    }

    //优化
    public int numSquares1(int n) {
        //题目可以理解为从i个平方数中选择，使得平方数的和恰好为n的完全平方数的最少数量
        //平方数的值为体积和价值，n为背包容量
        int aim = (int)Math.sqrt(n),INF = 0x3f3f3f3f;
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = INF;
        for (int i = 1; i <= aim; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}
